class Solution {
public:
    bool belong(TreeNode* root,TreeNode* find){
        if(root==NULL) return false;
        if(root==find) return true;
        return belong(root->left,find)||belong(root->right,find);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(belong(p,q)) return p;
        if(belong(q,p)) return q;
        if((belong(root->left,q)&&belong(root->right,p))||(belong(root->left,p)&&belong(root->right,q))) return root;//3.
        if(belong(root->left,q)||belong(root->left,p)) return lowestCommonAncestor(root->left,p,q);
        else return lowestCommonAncestor(root->right,p,q);
}
};